package lcr;

public class Test0095 {
    public static void main(String[] args) {
        new Solution0095_1().longestCommonSubsequence("abcba", "abcbcba");
    }
}

class Solution0095_1 {
    public int longestCommonSubsequence(String text1, String text2) {
        char[] chars1 = text1.toCharArray();
        char[] chars2 = text2.toCharArray();
        int length1 = chars1.length, length2 = chars2.length;
        int[] pre = new int[length2+1];
        int[] cur = new int[length2+1];
        for (char c1 : chars1) {
            for (int j = 1; j <= length2; j++) {
                char c2 = chars2[j - 1];

                if (c2 == c1) {
                    cur[j] = pre[j - 1] + 1;
                } else {
                    cur[j] = Math.max(pre[j], cur[j - 1]);
                }

            }
            int[] temp = pre;
            pre=cur;
            cur=temp;
        }

        return pre[length2];

    }
}
